# 2. 的 dp 写法
from typing import List

# 70左右
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        cache = {}
        w = len(grid)
        h = len(grid[0])
        for x in range(w):
            for y in range(h):
                curr = grid[x][y]
                t = (x, y)
                if x == 0 and y == 0:
                    cache[t] = curr
                if x > 0 and y > 0:
                    cache[t] = min(cache[(x - 1, y)] + curr, cache[(x, y - 1)] + curr)
                if x > 0 and y == 0:
                    cache[t] = cache[(x - 1, y)] + curr
                if x == 0 and y > 0:
                    cache[t] = cache[(x, y - 1)] + curr

        return cache[(w-1,h-1)]

solu = Solution()
# print(solu.minPathSum([
#   [1,3,1],
#   [1,5,1],
#   [4,2,1]
# ]))

print(solu.minPathSum([
    [1, 2, 3],
    [4, 5, 6]
]))
